(Problem) 001 Multiples of 3 and 5

작성일 In 댓글:

Project Euler

  • 공식 홈페이지 - projecteuler.net
  • 한글 번역 - projecteuler @kr
  • (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Multiples of 3 and 5


problem <번역>

solution

Simple Code

반복문을 통해 3과 5로 나누어 떨어지는 것들만 조건문을 통해 합하면 된다

001_multiples_of_3_and_5.py
def multiples_3_5(N):
    return sum([num for num in range(N) if (num % 3 == 0 or num % 5 == 0)])

print(multiples_3_5(1000))
HackerRank

HackerRank에 등록된 테스트 케이스들은 해당 문제의 풀이를 조금 더 까다롭게 검사한다.
이번 문제에서 위 풀이를 사용하면 TestCase 2, 3에서 ‘Terminated due to timeout’ 에러를 발생 시킨다.(아래 코드는 테스트 케이스를 입력 받는 부분만 추가한 것)
즉, 최적화된 방법으로 문제를 풀어야 한다.

Terminated due to timeout
def multiples_3_5(N):
    return sum([num for num in range(N) if (num % 3 == 0 or num % 5 == 0)])

if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N = int(input())
        print(multiples_3_5(N))

arithmetic sequence - mathsisfun.com
반복문을 제거해서 시간 복잡도를 O(1)로 바꿔준다. (등차수열을 활용해 결과를 한번에 구한다)
주의할 것은 등차수열의 개수를 구할 때 // 연산자를 사용하는 것이 좋다.(int((N-1)/3) 이렇게 구하면 안된다)

001_for_HacerRank.py
def arithmetic_sequence(mul):
    return mul * (mul + 1)

T = int(input())
for _ in range(T):
    N = int(input())

    mul_3 = (N-1) // 3
    mul_5 = (N-1) // 5
    mul_15 = (N-1) // 15 # lcm of 3, 5 = 15
    print((3 * arithmetic_sequence(mul_3) + 5 * arithmetic_sequence(mul_5) - 15 * arithmetic_sequence(mul_15)) // 2)

가독성(readability)을 생각했을 때, 반복문을 사용한 방법이 더 좋은 것 같지만 본 프로젝트의 의도가 수학적인 해결 방법을 고민해 보는 것이기 때문에 아래의 풀이 방법을 정확히 이해하는 것이 중요하다